#!/usr/bin/env python
#-*- coding: utf-8 -*-
#__author__:vincentlc
#time: 16/4/10 : 10:16


"""
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following is not:
    1
   / \
  2   2
   \   \
   3    3
Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
"""


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root==None:
            return True
        else:
            flag = self.isEqual(root.left,root.right)
            return flag
            # if flag:
            #     return True
            # else:
            #     return False

    def isEqual(self,root1,root2):
        """
        :param root1:TreeNode
        :param root2:TreeNode
        :return:bool
        """
        if root1==None and root2 != None or root2==None and root1!=None:
            return False

        if root1 == None and root2 == None:
            return True

        if root1.val != root2.val:
            return False
        else:
            flag1 = self.isEqual(root1.left,root2.right)
            flag2 = self.isEqual(root1.right,root2.left)
            if flag1 and flag2:
                return True
            else:
                return False


